package com.lwg.datastructure.commonSortingAlgorithm;

import java.util.Arrays;

/**
 * @author: lwg
 * @Date: 2022/4/22 22:58
 * @Description: 归并排序
 * 先递归拆开，有左中右 三个指针
 * 合并，比较分开的数，进行合并
 */
public class MergeSort {
    
    public static void main(String[] args) {
        int[] arr = {3, -1, 5, 4, 6, 1, 10, 20};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void mergeSort(int[] arr, int left, int right) {
        if (right - left + 1 == 1) {
            return;
        }
        // 求出中间值
        int mid = left+((right-left ) >> 1);
        //递归左边
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        //合并
        merge(arr, left, mid, right);
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        // 第一个归并段的开始
        int s1 = left;
        //第二个归并段的开始
        int s2 = mid + 1;
        // 临时的数组
        int[] res = new int[right - left + 1];
        //数组的下标
        int i = 0;
        //不超出索引的位置,递归的有数
        while (s1 <= mid && s2 <= right) {
            if (arr[s1] <= arr[s2]) {
                res[i++] = arr[s1++];
            } else {
                // 当s2中的数小于s1中 的数，第一次即 s2=-1, s1=3
                res[i++] = arr[s2++];
            }
        }
        //当s1排完了，将s2剩下的放入数组中
        while (s1 <= mid) {
            res[i++] = arr[s1++];
        }
        while (s2 <= right) {
            res[i++] = arr[s2++];
        }
        // 按照顺序放入数组中
        for (int j = 0; j < res.length; j++) {
            arr[j + left] = res[j];
        }
        
    }
}
